package 单周赛.december;

import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @
 * @date 2023/12/24
 */
public class 第377场单周赛 {

    public static void main(String[] args) {

        //m = 4, n = 3, hFences = [2,3], vFences = [2]
        System.out.println(maximizeSquareArea(4, 3, new int[]{2, 3},
                new int[]{2}));

        // source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2]

        final 第377场单周赛 impl = new 第377场单周赛();
        System.out.println(impl.minimumCost("abcd", "acbe",
                new char[]{'a', 'b', 'c', 'c', 'e', 'd'},
                new char[]{'b', 'c', 'b', 'e', 'b', 'e'},
                new int[]{2, 5, 5, 1, 2, 20}));

        //输入：
        //"aaaabadaaa"
        //"dbdadddbad"
        //["c","a","c","a","a","b","b","b","d","d","c"]
        //["a","c","b","d","b","c","a","d","c","b","d"]
        //[7,8,11,9,7,6,4,6,9,5,9]
        //输出：
        //187
        //预期：
        //56
    }

    public int[] numberGame(int[] nums) {
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i += 2) {
            int t = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = t;
        }

        return nums;
    }


    public static int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
        int mod = 1000000007;

        int[] hArr = new int[hFences.length + 2];
        System.arraycopy(hFences, 0, hArr, 0, hFences.length);
        hArr[hArr.length - 1] = 1;
        hArr[hArr.length - 2] = m;

        Set<Integer> hSet = new HashSet<>();
        for (int i = 1; i < hArr.length; i++) {
            for (int j = 0; j < i; j++) {
                hSet.add(Math.abs(hArr[j] - hArr[i]));
            }
        }

        int[] vArr = new int[vFences.length + 2];
        System.arraycopy(vFences, 0, vArr, 0, vFences.length);
        vArr[vArr.length - 1] = 1;
        vArr[vArr.length - 2] = n;

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> b - a);

        for (int i = 1; i < vArr.length; i++) {
            for (int j = 0; j < i; j++) {
                priorityQueue.add(Math.abs(vArr[j] - vArr[i]));
            }
        }

        while (!priorityQueue.isEmpty()) {

            Integer cur = priorityQueue.poll();
            if (hSet.contains(cur)) {
                // 注意：后面要加大括号！！！
                return (int) (1L * (cur % mod) * (cur % mod) % mod);
            }
        }
        return -1;
    }

    public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
        // record[i][j] 代表 original[i] 变成 changed[j] 的代价为 cos，不经过第 3 个节点的情况下
        int[][] record = new int[26][26];

        for (int o = 0; o < original.length; o++) {
            int i = original[o] - 'a', j = changed[o] - 'a';
            if (record[i][j] == 0) {
                record[i][j] = cost[o];
                continue;
            }
            record[i][j] = Math.min(record[i][j], cost[0]);
        }

        int sumCost = 0;
        int[][] r = new int[26][26];
        for (int s = 0; s < source.length(); s++) {
            int i = source.charAt(s) - 'a', j = target.charAt(s) - 'a';
            if (r[i][j] == 0) {

                targetJ = j;
                minCost = Integer.MAX_VALUE;
                int curCost = dfs(i, record, new boolean[26][26], 0);

                if (curCost == Integer.MAX_VALUE) {
                    return -1;
                }
                r[i][j] = curCost;
            }
            sumCost += r[i][j];
        }


        return sumCost;
    }

    private int targetJ;

    int minCost = Integer.MAX_VALUE;

    private int dfs(int i, int[][] record, boolean[][] visited, int preCost) {
        if (i == targetJ) {
            return preCost;
        }
        if (preCost > minCost) {
            return minCost;
        }

        for (int j = 0; j < 26; j++) {
            if (visited[i][j]) {
                continue;
            }
            if (record[i][j] == 0) {
                continue;
            }
            visited[i][j] = true;
            minCost = Math.min(minCost, dfs(j, record, visited, preCost + record[i][j]));
            visited[i][j] = false;
        }
        return minCost;
    }

}
